package com.bravo.other.knapsack;

/**
 * 线性规划算法
 * 最大价值
 * 最多个数
 * 最大重量
 * 装满背包最小个数
 *
 *
 */
public class Learn {

    /**
     * @param args
     */
    public static void main(String[] args) {

        int a = 5;
        int b = 11;
        int c = b / a;
        System.out.println("c=" + c);

        // wholeKnapsackProblem();
//         knapsackProblem1();
        oneDimension();
    }

    // 以为数组解决 0-1 背包问题
    public static void oneDimension() {
        int[] w = {2, 2, 4, 6, 3};   // 重量
        int[] v = {3, 4, 5, 6, 7};   // 体积
        int n = w.length;

        int W = 10; // 背包容量

        int[] dp = new int[W + 1];
        // 循环查询
        // 循环物品
        for (int i = 0; i < n; i++) {
            // 第二次 循环背包
            for (int j = W; j > w[i]; j--) {

                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);

            }
        }
        System.out.println("dp[w] = " + dp[W]);

    }


    /**
     * 完全背包问题
     * 每个物品可以选多次
     * 重复物品是否可以考虑重量和价值比公式
     * 一维代表 背包容量
     * 二维代表 新增的物品
     * <p>
     * 01背包问题的状态和转移方程：
     *
     *
     */
    public static void wholeKnapsackProblem() {
        int[] w = {2, 2, 4, 6, 3};
        int[] v = {3, 4, 5, 6, 7};
        int n = w.length;


        int W = 10; // 背包容量
        int[][] dp = new int[n][W + 1];
        // 背包容量增加
        for (int i = 0; i <= W; i++) {
            //
            if (i >= w[0]) {

                dp[0][i] = dp[0][i - w[0]] + v[0]; // 可以重复选物品0
                // dp[0][i] = (i / w[0]) * v[0];
            }
        }
        // 物品增加
        for (int i = 1; i < n; i++) {
            // 背包容量增加
            for (int k = 0; k <= W; k++) {
                if (k >= w[i]) {
                    dp[i][k] = Math.max(dp[i - 1][k], dp[i][k - w[i]] + v[i]);
                } else {
                    dp[i][k] = dp[i - 1][k];
                }

            }
        }

        printArray2(dp);

    }


    // 推导式  dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] +
    //  如果允许多次 那么第一次 就是对一个物品一直取余数
    // 背包容量增加 就计算 上一次
    // 状态转移方程： dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
    // dp[i-1][j-w[i] = dp[i-1][j-w[i]] + v[i]]


    /**
     * 背包问题（Knapsack Problem）是经典的动态规划问题。其核心是：有一个容量为 (W) 的背包和 (n) 个物品，每个物品有重量 (w_i) 和价值 (v_i)，问如何选择物品放入背包，使得总价值最大，且总重量不超过背包容量。
     * <p>
     * 常见的有两种类型：
     * <p>
     * <p>
     * 0-1 背包：每个物品只能选一次。
     * 完全背包：每个物品可以选多次。
     * 0-1 背包问题动态规划思路：
     * <p>
     * <p>
     * 定义状态：dp[i][j] 表示前 i 个物品，背包容量为 j 时的最大价值。
     * 状态转移：
     * 不选第 i 个物品：dp[i][j] = dp[i-1][j]
     * 选第 i 个物品（如果容量够）：dp[i][j] = dp[i-1][j-w[i]] + v[i]
     * 递推公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
     * public static void knapsackProblem1() {
     * // 物品重量
     * int [] w= {1, 3, 4,3,3};
     * int [] v= {15, 20, 30,10,5};
     * <p>
     * int n = w.length;
     * int j=v.length;
     * <p>
     * int W = 10; // 背包容量
     * int [][] dp = new int[n][W+1];
     * // 遍历背包 不同背包
     * for (int i = 0; i < n; i++) {
     * for (int k = 0; k <  j; k++) {
     * <p>
     * // 背包能否放下物品
     * if (k>=w[i]){
     * dp[i][k] = Math.max(dp[i-1][k], dp[i-1][k-w[i]] + v[i]);
     * }else {
     * dp[i][k] = dp[i-1][k];
     * }
     * <p>
     * System.out.println("dp["+i+"]["+k+"]="+dp[i][k]);
     * }
     * }
     * }
     *
     *
     *
     *
     *
     *
     */


    public static int solution(int n, int A, int B, int[] array_a) {
        // Please write your code here
        // 如果容量不够
        // 对10取余 就是个位数
        //
        int sum = 0;
        int typeSize = 0;
        int small = Math.min(A, B);
        int big = Math.max(A, B);
        // 个位数
        for (int i = 0; i < n; i++) {
            sum += array_a[i];
        }
        int totalMod = sum % 10;
        // 特殊情况 一种

        int[][] dp = new int[array_a.length][10];
        // 一般情况
        if ((A + B) % 10 == totalMod) {
            // 动态规划 计算
            sum = 0;
            dp[0][0] = 1;
            for (int i = 1; i < array_a.length+1; i++) {
                if (i == 1) {
                    dp[0][1] = 1;
                    dp[0][array_a[0]] = 1;
                } else {
                    for (int j = 0; j < 10; j++) {
                        dp[i][j] += dp[i - 1][j];
                         // 原有的值也不能变
                        dp[i][(j+array_a[i])%10] +=dp[i-1][j];

                    }
                }

            }
            sum+=dp[n][A];
            if (A!=B) {
                sum+=dp[n][B];
            }
            return sum;
        }


        return 0;
    }


    public static void knapsackProblem1() {
        // 物品重量
        int[] w = {1, 3, 4, 3, 3};
        int[] v = {15, 20, 30, 10, 5};

        int n = w.length;
        int j = v.length;

        int W = 10; // 背包容量
        int[][] dp = new int[n][W + 1];

        // 第一列  第一个物品
        for (int i = 0; i <= W; i++) {
            if (i >= w[0]) {
                dp[0][i] = v[0];
            }
        }
        // 行列 式

        // 遍历物品
        for (int i = 1; i < n; i++) {
            for (int k = 0; k <= W; k++) {

                //
                if (k >= w[i]) {
                    dp[i][k] = Math.max(dp[i - 1][k], dp[i - 1][k - w[i]] + v[i]);
                } else {
                    dp[i][k] = dp[i - 1][k];
                }

                System.out.println("dp[" + i + "][" + k + "]=" + dp[i][k]);
            }
        }
        printArray2(dp);
    }
//    public static void knapsackProblem1() {
//        // do nothing
//        System.out.println("背包问题算法");
//        int W = 10;
//        int n = 5;
//        int[] w = {2, 2, 4, 6, 3}; // 物品重量
//        int[] v = {3, 5, 11, 6, 1}; // 物品价值
//        int[][] dp = new int[n + 1][W + 1];
//        // 遍历物品
//        for (int i = 1; i <= n; i++) {
//            // 遍历背包容量
//            for (int j = 0; j <= W; j++) {
//                // 不选第 i 个物品
//                // dp[i][j] = dp[i-1][j];
//                // 选第 i 个物品（如果容量够）
//                // dp[i][j] = dp[i-1][j-w[i]] + v
//                if (j >= w[i - 1]) {
//                    // 递推公式
//                    // 上一个背包（i的上一个数据 同背包容量的价值）中的最大价值 和 当前物品价值加 前物品重量的背包中的最大价值 取最大值
//                    // 背包容量-物品重量+物品价值
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
//                } else {
//                    dp[i][j] = dp[i - 1][j];
//                }
//
//            // 打印当前 dp 数组
//            System.out.println("i=" + i + ", j=" + j + " 时 dp 数组：");
//            for (int x = 0; x <= n; x++) {
//                for (int y = 0; y <= W; y++) {
//                    System.out.print(dp[x][y] + "\t");
//                }
//                System.out.println();
//            }
//            System.out.println("-----------------------------");
//
//            }
//
//        }
//        System.out.println("最大价值：" + dp[n][W]);
//    }


    // 美化打印方法2：表格形式对齐打印
    public static void printArray2(int[][] array) {
        // 打印列索引
        System.out.print("     ");
        for (int j = 0; j < array[0].length; j++) {
            System.out.printf("%4d", j);
        }
        System.out.println();

        // 打印分隔线
        System.out.print("     ");
        for (int j = 0; j < array[0].length; j++) {
            System.out.print("----");
        }
        System.out.println();

        // 打印每行数据
        for (int i = 0; i < array.length; i++) {
            System.out.printf("%3d| ", i);
            for (int j = 0; j < array[i].length; j++) {
                System.out.printf("%4d", array[i][j]);
            }
            System.out.println();
        }
    }
}

